package com.wangbo.sort;

/**
 * 插入排序（从小到大排列）
 * 两个指针
 */
public class InsertionSort {
    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        // p1: 遍历指针，从数组第二个元素遍历到数组末尾
        for (int p1 = 1; p1 < arr.length; p1++) {
            // p2: 遍历指针，初始值为 p1, 向左遍历，当 p2 所指元素 大于等于 p2-1 所指元素 ，或者 p2 指向数组头时，停止遍历
            for (int p2 = p1; p2 > 0 && arr[p2] < arr[p2 - 1]; p2--) {
                swap(arr, p2, p2 - 1);
            }
        }
    }

    /**
     * 交换指针对象
     */
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
